<!DOCTYPE html>
<!-- saved from url=(0040)file:///C:/Users/gm/Desktop/ll1/ll1.html -->
<html><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
    <title>LL(1) Parser Generator</title>
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    
    <style>
        td {
            horizontal-align: middle;
            vertical-align: middle;
        }

        .node {
            stroke: #fff;
            stroke-width: 2px;
        }

        .link {
            fill: none;
            stroke: #000;
        }
    </style>

    <script src="./index_files/d3.js.下载"></script>


    <link rel="stylesheet" href="./index_files/pure-min.css" integrity="sha384-oAOxQR6DkCoMliIh8yFnu25d7Eq/PHS21PClpwjOTeU2jRSq11vu66rf90/cZr47" crossorigin="anonymous">
    <link rel="stylesheet" href="./index_files/grids-responsive-min.css">
    <link rel="stylesheet" href="./index_files/sty.css">

</head>
<body>


<div class="header">
    <h1>LL(1) Parser Visualization</h1>
    <h2>Write your own context-free grammar and see an LL(1) parser in action!</h2>
    <p> Written by Zak Kincaid and Shaowei Zhu based on http://jsmachines.sourceforge.net/machines/ll1.html</p>
</div>

<div class="content">


    <h2 class="content-subhead">1. Write your LL(1) grammar (empty string '' represents ε):</h2>

    <div class="pure-g">
        <div class="pure-u-1 pure-u-md-1-3">
	  <textarea class="pure-input-1" id="grammar" rows="15" cols="20">E ::= T E'
E' ::= + T E'
E' ::= ''
T ::= F T'
T' ::= * F T'
T' ::= ''
F ::= ( E )
F ::= id</textarea>
        </div>
        <div class="pure-u-1 pure-u-md-2-3">
            <h4>
                Valid LL(1) Grammars
            </h4>
            <p>For any production S -&gt; A | B, it must be the case that:</p>
            <ul>
                <li>For no terminal t could A and B derive strings beginning with t</li>
                <li>At most one of A and B can derive the empty string</li>
                <li>if B can derive the empty string, then A does not derive any string beginning with a terminal in
                    Follow(A)
                </li>
            </ul>
            <h4>
                Formatting Instructions
            </h4>
            <ul>
                <li>The non-terminal on the left-hand-side of the first rule is the start non-terminal</li>
                <li>Write each production rule in a separate line (see example to the left)</li>
                <li>Separate each token using whitespace</li>
                <li>$ is reserved as the end-of-input symbol, and S is reserved as an artificial start symbol. The
                    grammar is automatically augmented with the rule S ::= <i>start</i> $
                </li>
            </ul>
            <h4>
                Debugging
            </h4>
            <ul>
                <li>More information about the parser construction is printed on the console</li>
                <li>The source code follows the pseudocode in lecture. In particular, see <tt>computeNullable</tt>, <tt>computeFirst</tt>,
                    <tt>computeFollow</tt>, and <tt>computeLL1Tables</tt></li>
            </ul>
        </div>

    </div>

    <br>

    <a class="pure-button pure-button-primary" onclick="grammarChanged();">Generate tables</a>


    <h2 class="content-subhead">2. Nullable/First/Follow Table and Transition Table</h2>

    <table class="pure-table">
        <tbody>
        <tr>
            <td>
                <table class="pure-table pure-table-bordered">
                    <thead>
                    <tr id="firstFollowTableHead"><th>Nonterminal</th><th>Nullable?</th><th>First</th><th>Follow</th></tr>
                    </thead>
                    <tbody id="firstFollowTableRows"><tr></tr><tr><td nowrap="nowrap">S</td><td nowrap="nowrap">✖</td><td nowrap="nowrap">(, id</td><td nowrap="nowrap"></td></tr><tr></tr><tr><td nowrap="nowrap">E</td><td nowrap="nowrap">✖</td><td nowrap="nowrap">(, id</td><td nowrap="nowrap">), $</td></tr><tr></tr><tr><td nowrap="nowrap">E'</td><td nowrap="nowrap">✔</td><td nowrap="nowrap">+</td><td nowrap="nowrap">), $</td></tr><tr></tr><tr><td nowrap="nowrap">T</td><td nowrap="nowrap">✖</td><td nowrap="nowrap">(, id</td><td nowrap="nowrap">+, ), $</td></tr><tr></tr><tr><td nowrap="nowrap">T'</td><td nowrap="nowrap">✔</td><td nowrap="nowrap">*</td><td nowrap="nowrap">+, ), $</td></tr><tr></tr><tr><td nowrap="nowrap">F</td><td nowrap="nowrap">✖</td><td nowrap="nowrap">(, id</td><td nowrap="nowrap">+, *, ), $</td></tr></tbody>
                </table>
            </td>
            <td>
                <table class="pure-table pure-table-bordered" border="1">
                    <thead>
                    <tr id="llTableHead"><th></th><th>$</th><th>+</th><th>*</th><th>(</th><th>)</th><th>id</th></tr></thead>
                    <tbody id="llTableRows"><tr></tr><tr><td nowrap="nowrap">S</td><td nowrap="nowrap"></td><td nowrap="nowrap"></td><td nowrap="nowrap"></td><td nowrap="nowrap">S ::= E $</td><td nowrap="nowrap"></td><td nowrap="nowrap">S ::= E $</td></tr><tr></tr><tr><td nowrap="nowrap">E</td><td nowrap="nowrap"></td><td nowrap="nowrap"></td><td nowrap="nowrap"></td><td nowrap="nowrap">E ::= T E'</td><td nowrap="nowrap"></td><td nowrap="nowrap">E ::= T E'</td></tr><tr></tr><tr><td nowrap="nowrap">E'</td><td nowrap="nowrap">E' ::= ε</td><td nowrap="nowrap">E' ::= + T E'</td><td nowrap="nowrap"></td><td nowrap="nowrap"></td><td nowrap="nowrap">E' ::= ε</td><td nowrap="nowrap"></td></tr><tr></tr><tr><td nowrap="nowrap">T</td><td nowrap="nowrap"></td><td nowrap="nowrap"></td><td nowrap="nowrap"></td><td nowrap="nowrap">T ::= F T'</td><td nowrap="nowrap"></td><td nowrap="nowrap">T ::= F T'</td></tr><tr></tr><tr><td nowrap="nowrap">T'</td><td nowrap="nowrap">T' ::= ε</td><td nowrap="nowrap">T' ::= ε</td><td nowrap="nowrap">T' ::= * F T'</td><td nowrap="nowrap"></td><td nowrap="nowrap">T' ::= ε</td><td nowrap="nowrap"></td></tr><tr></tr><tr><td nowrap="nowrap">F</td><td nowrap="nowrap"></td><td nowrap="nowrap"></td><td nowrap="nowrap"></td><td nowrap="nowrap">F ::= ( E )</td><td nowrap="nowrap"></td><td nowrap="nowrap">F ::= id</td></tr></tbody>
                </table>
            </td>

        </tr>
        </tbody>
    </table>


    <h2 class="content-subhead">3. Parsing</h2>

    <form class="pure-form pure-form-aligned">
        <fieldset>
            <div class="pure-control-group">
                <label for="input">Token stream separated by spaces: </label>
                <input id="input" type="text" size="11" onkeyup="resize(this, 10);" value="id + id" data-com.bitwarden.browser.user-edited="yes" style="color: green;">
            </div>
            <a class="pure-button pure-button-primary" onclick="parseInputStart();"> Start/Reset </a>
            <a id="stepButton" class="pure-button pure-button-primary" onclick="parseInputStep();"> Step
                Forward </a>
        </fieldset>
    </form>

    <br>

    <br>

    <div class="pure-g">
        <div class="pure-u-1 pure-u-md-1-4">
            <form class="pure-form pure-form-stacked">
                <fieldset>
                    <div class="pure-control-group">
                        <label for="stack">Stack</label>
                        <input id="stack" type="text" size="10" readonly="" value="">
                    </div>
                    <div class="pure-control-group">
                        <label for="remInput">Remaining Input</label>
                        <input id="remInput" type="text" size="10" readonly="" value="">
                    </div>
                    <div class="pure-control-group">
                        <label for="remInput">Rule</label>
                        <input id="ruleDisplay" type="text" size="10" readonly="" value="">
                    </div>
                </fieldset>
            </form>
        </div>
        <div class="pure-u-1 pure-u-md-3-4">
            <h3> Partial Parse Tree</h3>
            <svg width="800" height="600"><svg width="800" height="400"><g transform="translate(20, 20)"><text dx=".5em" font-family="serif" font-size="20px" y="0" x="447.77777777777777">E</text><text dx=".5em" font-family="serif" font-size="20px" x="288.8888888888889" y="58.333333333333336">T</text><path class="link" d="M447.77777777777777,0C447.77777777777777,29.166666666666668 288.8888888888889,29.166666666666668 288.8888888888889,58.333333333333336"></path><text dx=".5em" font-family="serif" font-size="20px" x="606.6666666666666" y="58.333333333333336">E'</text><path class="link" d="M447.77777777777777,0C447.77777777777777,29.166666666666668 606.6666666666666,29.166666666666668 606.6666666666666,58.333333333333336"></path><text dx=".5em" font-family="serif" font-size="20px" x="202.22222222222223" y="116.66666666666667">F</text><path class="link" d="M288.8888888888889,58.333333333333336C288.8888888888889,87.5 202.22222222222223,87.5 202.22222222222223,116.66666666666667"></path><text dx=".5em" font-family="serif" font-size="20px" x="375.55555555555554" y="116.66666666666667">T'</text><path class="link" d="M288.8888888888889,58.333333333333336C288.8888888888889,87.5 375.55555555555554,87.5 375.55555555555554,116.66666666666667"></path><text dx=".5em" font-family="serif" font-size="20px" x="144.44444444444446" y="175">(</text><path class="link" d="M202.22222222222223,116.66666666666667C202.22222222222223,145.83333333333334 144.44444444444446,145.83333333333334 144.44444444444446,175"></path><text dx=".5em" font-family="serif" font-size="20px" x="202.22222222222223" y="175">E</text><path class="link" d="M202.22222222222223,116.66666666666667C202.22222222222223,145.83333333333334 202.22222222222223,145.83333333333334 202.22222222222223,175"></path><text dx=".5em" font-family="serif" font-size="20px" x="260" y="175">)</text><path class="link" d="M202.22222222222223,116.66666666666667C202.22222222222223,145.83333333333334 260,145.83333333333334 260,175"></path><text dx=".5em" font-family="serif" font-size="20px" x="115.55555555555556" y="233.33333333333334">T</text><path class="link" d="M202.22222222222223,175C202.22222222222223,204.16666666666669 115.55555555555556,204.16666666666669 115.55555555555556,233.33333333333334"></path><text dx=".5em" font-family="serif" font-size="20px" x="288.8888888888889" y="233.33333333333334">E'</text><path class="link" d="M202.22222222222223,175C202.22222222222223,204.16666666666669 288.8888888888889,204.16666666666669 288.8888888888889,233.33333333333334"></path><text dx=".5em" font-family="serif" font-size="20px" x="57.77777777777778" y="291.6666666666667">F</text><path class="link" d="M115.55555555555556,233.33333333333334C115.55555555555556,262.5 57.77777777777778,262.5 57.77777777777778,291.6666666666667"></path><text dx=".5em" font-family="serif" font-size="20px" x="173.33333333333334" y="291.6666666666667">T'</text><path class="link" d="M115.55555555555556,233.33333333333334C115.55555555555556,262.5 173.33333333333334,262.5 173.33333333333334,291.6666666666667"></path><text dx=".5em" font-family="serif" font-size="20px" x="57.77777777777778" y="350">id</text><path class="link" d="M57.77777777777778,291.6666666666667C57.77777777777778,320.83333333333337 57.77777777777778,320.83333333333337 57.77777777777778,350"></path><text dx=".5em" font-family="serif" font-size="20px" x="173.33333333333334" y="350">ε</text><path class="link" d="M173.33333333333334,291.6666666666667C173.33333333333334,320.83333333333337 173.33333333333334,320.83333333333337 173.33333333333334,350"></path><text dx=".5em" font-family="serif" font-size="20px" x="288.8888888888889" y="291.6666666666667">ε</text><path class="link" d="M288.8888888888889,233.33333333333334C288.8888888888889,262.5 288.8888888888889,262.5 288.8888888888889,291.6666666666667"></path><text dx=".5em" font-family="serif" font-size="20px" x="375.55555555555554" y="175">ε</text><path class="link" d="M375.55555555555554,116.66666666666667C375.55555555555554,145.83333333333334 375.55555555555554,145.83333333333334 375.55555555555554,175"></path><text dx=".5em" font-family="serif" font-size="20px" x="491.11111111111114" y="116.66666666666667">+</text><path class="link" d="M606.6666666666666,58.333333333333336C606.6666666666666,87.5 491.11111111111114,87.5 491.11111111111114,116.66666666666667"></path><text dx=".5em" font-family="serif" font-size="20px" x="548.8888888888889" y="116.66666666666667">T</text><path class="link" d="M606.6666666666666,58.333333333333336C606.6666666666666,87.5 548.8888888888889,87.5 548.8888888888889,116.66666666666667"></path><text dx=".5em" font-family="serif" font-size="20px" x="722.2222222222223" y="116.66666666666667">E'</text><path class="link" d="M606.6666666666666,58.333333333333336C606.6666666666666,87.5 722.2222222222223,87.5 722.2222222222223,116.66666666666667"></path><text dx=".5em" font-family="serif" font-size="20px" x="491.11111111111114" y="175">F</text><path class="link" d="M548.8888888888889,116.66666666666667C548.8888888888889,145.83333333333334 491.11111111111114,145.83333333333334 491.11111111111114,175"></path><text dx=".5em" font-family="serif" font-size="20px" x="606.6666666666666" y="175">T'</text><path class="link" d="M548.8888888888889,116.66666666666667C548.8888888888889,145.83333333333334 606.6666666666666,145.83333333333334 606.6666666666666,175"></path><text dx=".5em" font-family="serif" font-size="20px" x="491.11111111111114" y="233.33333333333334">id</text><path class="link" d="M491.11111111111114,175C491.11111111111114,204.16666666666669 491.11111111111114,204.16666666666669 491.11111111111114,233.33333333333334"></path><text dx=".5em" font-family="serif" font-size="20px" x="606.6666666666666" y="233.33333333333334">ε</text><path class="link" d="M606.6666666666666,175C606.6666666666666,204.16666666666669 606.6666666666666,204.16666666666669 606.6666666666666,233.33333333333334"></path><text dx=".5em" font-family="serif" font-size="20px" x="722.2222222222223" y="175">ε</text><path class="link" d="M722.2222222222223,116.66666666666667C722.2222222222223,145.83333333333334 722.2222222222223,145.83333333333334 722.2222222222223,175"></path></g></svg><svg width="800" height="400"><g transform="translate(20, 20)"></g></svg><svg width="800" height="400"><g transform="translate(20, 20)"></g></svg></svg>
        </div>
    </div>


</div>

<script language="javascript">
    var EPSILON = '\'\'';      // Input representation of empty string

    var synthetic_start = 'S'; // Artificial start non-terminal
    var sentinel = '$';        // End-of-input sentinel

    var state;                 // state of the parser
    var grammar;
    var nullable;              // set of nullable nonterminals
    var first;                 // first table
    var follow;                // follow table
    var transition;            // transition table

    function $element(id) {
        return document.getElementById(id);
    }

    function union(set1, set2) {
        let u = new Set(set1);
        for (let elt of set2) {
            u.add(elt);
        }
        return u;
    }

    // Given a map m from keys to sets of elements, add elt to m[key]
    // if elt was not already in m[key], set the m.changed flag
    function addToSetMap(m, key, elt) {
        if (!m[key].has(elt)) {
            m[key].add(elt);
            m.changed = true;
        }
    }

    function computeNullable(grammar) {
        console.log("Computing nullable...");
        var nullable = new Set();
        var fixpoint = false;
        var iteration = 0;
        while (!fixpoint) {
            fixpoint = true;
            for (rule of grammar.rules) {
                // RHS is nullable iff every symbol in the RHS is nullable
                if (rule.rhs.every(x => nullable.has(x))) {
                    if (!(nullable.has(rule.lhs))) {
                        nullable.add(rule.lhs);
                        fixpoint = false;
                    }
                }
            }
            console.log("  Nullable table @ iteration " + (++iteration));
            console.log("    " + Array.from(nullable).join(", "));
        }
        console.log("Done!");
        return nullable;
    }

    // compute first of a right-hand-side of a production (i.e., a
    // sequence of terminals and noterminals).
    function firstRhs(rhs, nullable, first) {
        // find longest nullable prefix
        var end = rhs.findIndex((sym) => !(nullable.has(sym)));
        if (end == -1) {
            end = rhs.length;
        }
        return rhs.slice(0, end + 1).map((sym) => first[sym]).reduce(union, new Set());
    }

    function computeFirst(grammar, nullable) {
        console.log("Computing first...");
        var first = {};

        // To simplify first/follow logic, define first(t) = {t} for any terminal t
        for (terminal of grammar.terminals) {
            first[terminal] = new Set([terminal]);
        }
        for (nonterminal of grammar.nonterminals) {
            first[nonterminal] = new Set();
        }

        first.changed = true;
        var iteration = 0;
        while (first.changed) {
            first.changed = false;
            for (rule of grammar.rules) {
                firstRhs(rule.rhs, nullable, first).forEach((terminal) =>
                    addToSetMap(first, rule.lhs, terminal));
            }
            console.log("  First table @ iteration " + (++iteration));
            console.log(stringOfSetMap(first, 4));

        }
        console.log("Done!");

        return first;
    }


    function computeFollow(grammar, nullable, first) {
        console.log("Computing follow...");

        var follow = {};
        for (nonterminal of grammar.nonterminals) {
            follow[nonterminal] = new Set();
        }
        follow.changed = true;
        var iteration = 0;
        while (follow.changed) {
            follow.changed = false;

            for (rule of grammar.rules) {

                // invariant: rule_follow is the follow set for position i of rule.rhs
                var rule_follow = follow[rule.lhs];
                for (i = rule.rhs.length - 1; i >= 0; i--) {
                    if (grammar.nonterminals.has(rule.rhs[i])) {
                        rule_follow.forEach(function (terminal) {
                            addToSetMap(follow, rule.rhs[i], terminal);
                        });
                    }
                    if (nullable.has(rule.rhs[i])) {
                        rule_follow = union(rule_follow, first[rule.rhs[i]]);
                    } else {
                        rule_follow = first[rule.rhs[i]];
                    }
                }
            }
            console.log("  Follow table @ iteration " + (++iteration));
            console.log(stringOfSetMap(follow, 4));
        }
        console.log("Done!");
        return follow;
    }

    function computeLL1Tables(grammar) {
        nullable = computeNullable(grammar);
        first = computeFirst(grammar, nullable);
        follow = computeFollow(grammar, nullable, first);

        // Compute transition table
        transition = {};
        for (n of grammar.nonterminals) {
            transition[n] = {};
            for (t of grammar.terminals) {
                transition[n][t] = [];
            }
        }
        for (rule of grammar.rules) {
            for (a of firstRhs(rule.rhs, nullable, first)) {
                transition[rule.lhs][a].push(rule);
            }

            if (rule.rhs.every(x => nullable.has(x))) {
                for (a of follow[rule.lhs]) {
                    transition[rule.lhs][a].push(rule);
                }
            }
        }
    }

    function grammarChanged() {
        var rules = [];
        var nonterminals = new Set(synthetic_start);
        for (var rule of $element('grammar').value.split('\n')) {
            let split_rule = rule.split('::=');
            if (split_rule.length == 2) {
                let lhs = split_rule[0].trim();
                let rhs = split_rule[1].trim().split(/\s+/).filter((x) => !(x == EPSILON));
                rules.push({
                    lhs,
                    rhs
                });
                nonterminals.add(lhs);
            }
        }

        var terminals = new Set(sentinel);
        for (rule of rules) {
            rule.rhs.forEach(function (symbol) {
                if (!(nonterminals.has(symbol))) {
                    terminals.add(symbol);
                }
            });
        }

        // Use the left hand side of the first rule as starting nonterminal
        start = rules[0].lhs;

        rules.push({
            lhs: synthetic_start,
            rhs: [start, sentinel]
        });

        grammar = {
            rules,
            terminals,
            nonterminals,
            start
        };

        computeLL1Tables(grammar);
        displayTables();
    }

    var ok; // parser state error?
    var tree;
    var parents;
    var index = 0;

    // precondition: nullable, first, follow, transition are already initialized
    function displayTables() {
        $element('firstFollowTableHead').innerHTML = "<th>Nonterminal</th><th>Nullable?</th><th>First</th><th>Follow</th>";
        $element('firstFollowTableRows').innerHTML = "";
        for (nonterminal of grammar.nonterminals) {
            var s = "<tr>";
            s += "<tr>";
            s += "<td nowrap=\"nowrap\">" + nonterminal + "</td>"
            s += "<td nowrap=\"nowrap\">" + (nullable.has(nonterminal) ? "&#10004;" : "&#10006;") + "</td>"
            s += "<td nowrap=\"nowrap\">" + Array.from(first[nonterminal]).join(", ") + "</td>"
            s += "<td nowrap=\"nowrap\">" + Array.from(follow[nonterminal]).join(", ") + "</td>";
            s += "</tr>";
            $element('firstFollowTableRows').innerHTML += s;
        }

        $element('llTableHead').innerHTML = "<th></th>";

        for (var terminal of grammar.terminals) {
            $element('llTableHead').innerHTML += "<th>" + terminal + "</th>";
        }

        $element('llTableRows').innerHTML = "";
        var conflict = false;
        for (var nonterminal of grammar.nonterminals) {
            var s = "<tr>";
            s += "<tr>";
            s += "<td nowrap=\"nowrap\">" + nonterminal + "</td>";

            for (var terminal of grammar.terminals) {
                var contents = transition[nonterminal][terminal]
                    .map(stringOfRule)
                    .join("<br />");

                if (transition[nonterminal][terminal].length > 1) {
                    s += "<td nowrap=\"nowrap\" style=\"color: white; background-color: red\">" + contents + "</td>";
                    conflict = true;
                } else {
                    s += "<td nowrap=\"nowrap\">" + contents + "</td>";
                }
            }

            s += "</tr>";

            $element('llTableRows').innerHTML += s;
        }

        if (conflict) {
            alert("Conflict detected. Grammar is not LL(1)!");
        }
    }

    function stringOfRule(rule) {
        if (rule.rhs.length == 0) {
            return rule.lhs + " ::= ε";
        } else {
            return rule.lhs + " ::= " + rule.rhs.join(' ');
        }
    }

    function stringOfSetMap(m, indent) {
        var s = "";
        for (key in m) {
            if (key != "changed") {
                s += " ".repeat(indent) + key + " -> " + Array.from(m[key]).join(", ") + "\n";
            }
        }
        return s;
    }

    function resize(textInput, minimumSize) {
        textInput.size = Math.max(minimumSize, textInput.value.length);
    }

    var w = 800,
        h = 400,
        root = {},
        d3tree = d3.layout.tree().size([w, h]),
        diagonal = d3.svg.diagonal(),
        duration = 250;
    var cnt = 0;

    var vis = d3.select("svg").append("svg")
        .attr("width", w)
        .attr("height", h)
        .append("g")
        .attr("transform", "translate(20, 20)");

    // Initialize parser state
    function parseInputStart() {

        // Place a $ token at the end of the input string
        input = $element('input').value.trim().split(/\s/).concat([sentinel]),

            stack = ['$', grammar.start];

        state = {
            position: 0,
            stack: stack,
            input: input,
            transition: transition,
            terminals: grammar.terminals,
            nonterminals: grammar.nonterminals
        };

        start = grammar.start;
        ok = true;

        /* Display code ********************************************************/
        parsingRows = '<tr><td nowrap=\"nowrap\">'
            + state.stack.join(' ')
            + "</td><td nowrap=\"nowrap\">"
            + state.input.join(' ')
            + " $</td nowrap=\"nowrap\"><td></td></tr>\n";

        tree = new Object();
        tree.label = 'root';
        tree.children = [];
        tree.name = start;
        index = 0;


        $element('ruleDisplay').value = "";
        resize($element('ruleDisplay'), 10);

        $element('stepButton').removeAttribute("disabled");

        d3.selectAll("svg > *").remove();
        vis = d3.select("svg").append("svg")
            .attr("width", w)
            .attr("height", h)
            .append("g")
            .attr("transform", "translate(20, 20)");
        d3tree = d3.layout.tree().size([w - 20, h - 50]);
        diagonal = d3.svg.diagonal();
        root = {
            label: 'root',
            id: "id0",
            children: []
        };
        cnt = 0;

        var pnode = new Object();
        pnode.label = start;
        pnode.children = [];
        pnode.id = "id" + (++cnt);
        pnode.parent = root;
        update(root, pnode);

        parents = [pnode];

        $element('stack').value = state.stack.join(' ');
        resize($element('stack'), 10);
        $element('remInput').value = state.input.slice(index).join(' ');
        resize($element('remInput'), 10);
        $element('input').style.color = ok ? 'green' : 'red';

    }

    // Execute one step of the parser.
    function parseInputStep() {
        if (state.position >= state.input.length) {
            alert("Parsing complete! Press reset to see it again.");
            return;
        }
        var top = state.stack.pop();
        var next = state.input[state.position];

        var rule = '';
        if (state.terminals.has(top)) {
            // If top of the stack matches next input character, consume the input
            if (next == top) {
                state.position++;
                parents.pop();

                $element('ruleDisplay').value = "Match " + next;
                resize($element('ruleDisplay'), 10);
            } else {
                ok = false;
                alert("Expected " + top + ", got " + next);
                return;
            }
        } else if (next in state.transition[top]) {
            var rule = state.transition[top][next][0];
            if (rule == undefined) {
                ok = false;
                alert("Syntax error when trying to expand elements at the top of the stack:\nNo valid transition from a nonterminal \"" + top + '\" with look ahead symbol \"' + next + "\"");
            }

            state.stack.push(...[].concat(rule.rhs).reverse());

            /* Display code ********************************************************/
            var p = parents.pop();
            childnodes = [];
            if (rule.rhs.length == 0) {
                var node = new Object();
                node.label = "ε";
                node.children = [];
                node.id = "id" + (++cnt);
                node.parent = p;
                update(p, node);
            } else {
                for (var i of rule.rhs) {
                    var node = new Object();
                    node.label = i;
                    node.children = [];
                    node.id = "id" + (++cnt);
                    node.parent = p;
                    update(p, node);
                    childnodes.push(node);
                }
            }
            parents = parents.concat(childnodes.reverse());
            $element('ruleDisplay').value = stringOfRule(rule);
            resize($element('ruleDisplay'), 10);

        } else {
            ok = false;
            alert("failure");
        }
        $element('stack').value = state.stack.join(' ');
        resize($element('stack'), 10);
        $element('remInput').value = state.input.slice(state.position).join(' ');
        resize($element('remInput'), 10);
        $element('input').style.color = ok ? 'green' : 'red';
    }


    function update(parent, cnode) {

        if (parent.children) {
            parent.children.push(cnode);
        } else {
            parent.children = [cnode];
        }

        // Compute the new tree layout. We'll stash the old layout in the data.
        var nodes = d3tree(root.children[0]);

        // Update the nodes…
        var node = vis.selectAll("text")
            .data(nodes, (d) => d.id);

        var nodeEnter = node.enter();

        nodeEnter.append('text')
            .attr("dx", ".5em")
            .attr("font-family", "serif")
            .attr("font-size", "20px")
            .text(function (d) {
                return d.label;
            })
            .attr("x", function (d) {
                return d.parent.x0;
            })
            .attr("y", function (d) {
                return d.parent.y0;
            })
            .transition()
            .duration(duration)
            .attr("x", d => d.x0 = d.x)
            .attr("y", d => d.y0 = d.y);


        node.exit().remove();

        node.transition()
            .duration(duration)
            .attr("x", d => d.x0 = d.x)
            .attr("y", d => d.y0 = d.y);

        // Update the links…
        var link = vis.selectAll("path.link")
            .data(d3tree.links(nodes), d => d.source.id + "-" + d.target.id);

        // Enter any new links at the parent's previous position.
        link.enter().insert("svg:path", "circle")
            .attr("class", "link")
            .attr("d", function (d) {
                var o = {
                    x: d.source.x0,
                    y: d.source.y0
                };
                return diagonal({
                    source: o,
                    target: o
                });
            })
            .transition()
            .duration(duration)
            .attr("d", diagonal);

        // Transition links to their new position.
        link.transition()
            .duration(duration)
            .attr("d", diagonal);
    }
</script>



<script language="javascript">
    grammarChanged();
</script>

</body></html>